package com.chj.dfs.class04;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Code03_PathSum {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean hasPathSum(Node root, int sum) {
		if (root == null) {
			return false;
		}
		if (root.left == null && root.right == null) {
			return root.value == sum;
		}

		return hasPathSum(root.left, sum - root.value) || hasPathSum(root.right, sum - root.value);
	}

	public static boolean hasPathSum02(Node root, int sum) {
		if (root == null) {
			return false;
		}
		return hasPathSumHelper(root, sum);
	}

	private static boolean hasPathSumHelper(Node root, int sum) {
		// 到达叶子节点
		if (root.left == null && root.right == null) {
			return root.value == sum;
		}
		// 左孩子为 null
		if (root.left == null) {
			return hasPathSumHelper(root.right, sum - root.value);
		}
		// 右孩子为 null
		if (root.right == null) {
			return hasPathSumHelper(root.left, sum - root.value);
		}
		return hasPathSumHelper(root.left, sum - root.value) || hasPathSumHelper(root.right, sum - root.value);
	}

	public static boolean hasPathSum03(Node root, int sum) {
		Queue<Node> queue = new LinkedList<Node>();
		Queue<Integer> queueSum = new LinkedList<Integer>();
		if (root == null)
			return false;
		// 安全的添加操作，在尾部添加
		queue.offer(root);
		queueSum.offer(root.value);
		while (!queue.isEmpty()) {
			int levelNum = queue.size(); // 当前层元素的个数
			for (int i = 0; i < levelNum; i++) {
				// 获取第一个，同时删除它
				Node curNode = queue.poll();
				int curSum = queueSum.poll();
				if (curNode != null) {
					// 判断叶子节点是否满足了条件
					if (curNode.left == null && curNode.right == null && curSum == sum) {
						return true;
					}
					// 当前节点和累计的和加入队列
					if (curNode.left != null) {
						queue.offer(curNode.left);
						queueSum.offer(curSum + curNode.left.value);
					}
					if (curNode.right != null) {
						queue.offer(curNode.right);
						queueSum.offer(curSum + curNode.right.value);
					}
				}
			}
		}
		return false;
	}

	public static boolean hasPathSum04(Node root, int sum) {
		Stack<Node> stack = new Stack<>();
		Stack<Integer> stackSum = new Stack<>();
		Node cur = root;
		int curSum = 0;
		while (cur != null || !stack.isEmpty()) {
			// 节点不为空一直压栈
			while (cur != null) {
				stack.push(cur);
				curSum += cur.value;
				stackSum.push(curSum);
				cur = cur.left; // 考虑左子树
			}
			// 节点为空，就出栈
			cur = stack.pop();
			curSum = stackSum.pop();
			// 判断是否满足条件
			if (curSum == sum && cur.left == null && cur.right == null) {
				return true;
			}
			// 考虑右子树
			cur = cur.right;
		}
		return false;
	}

	public static boolean hasPathSum05(Node root, int sum) {
		Stack<Node> toVisit = new Stack<>();
		Node cur = root;
		Node pre = null;
		int curSum = 0; // 记录当前的累计的和
		while (cur != null || !toVisit.isEmpty()) {
			while (cur != null) {
				toVisit.push(cur); // 添加根节点
				curSum += cur.value;
				cur = cur.left; // 递归添加左节点
			}
			cur = toVisit.peek(); // 已经访问到最左的节点了
			// 判断是否满足条件
			if (curSum == sum && cur.left == null && cur.right == null) {
				return true;
			}
			// 在不存在右节点或者右节点已经访问过的情况下，访问根节点
			if (cur.right == null || cur.right == pre) {
				Node pop = toVisit.pop();
				curSum -= pop.value; // 减去出栈的值
				pre = cur;
				cur = null;
			} else {
				cur = cur.right; // 右节点还没有访问过就先访问右节点
			}
		}
		return false;
	}

	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

	public static void main(String[] args) {
		Node head = new Node(5);
		head.left = new Node(4);
		head.right = new Node(8);
		head.left.left = new Node(11);
		head.right.left = new Node(13);
		head.right.right = new Node(4);
		head.right.right.right = new Node(1);
		head.left.left.left = new Node(7);
		head.left.left.right = new Node(2);
		printTree(head);

		System.out.println(hasPathSum(head, 22));
		System.out.println(hasPathSum02(head, 22));
		System.out.println(hasPathSum03(head, 22));
		System.out.println(hasPathSum04(head, 22));
		System.out.println(hasPathSum05(head, 22));
	}
}
